package cn.edu.xjtu.data_structure.chapter03_tree_and_binary_tree.btree;

/**
 * @author yjq
 * @version 1.0
 * @date 2021/9/21 20:24
 */
public class BinaryTreePtr {
    //利用指针实现二叉树
    private BinNodePtr root;//根结点

    public BinaryTreePtr(BinNodePtr root) {
        this.root = root;
    }
    public BinaryTreePtr() {
    }
    public void setRoot(BinNodePtr root) {
        this.root = root;
    }
    public BinNodePtr getRoot() {
        return root;
    }
    /**
     * 获得树高
     * @param root
     * @return
     */
    public int getHeight(BinNodePtr root){
        if (root==null)return 0;
        else {
            int lHeight = getHeight(root.getLeft());
            int rHeight = getHeight(root.getRight());
            if (lHeight>rHeight) return lHeight+1;
            else  return rHeight+1;
        }
    }
    /**
     * 递归删除结点
     * 为两种情况：如果删除的是叶结点，则删除该结点
     * 如果删除的是非叶结点，则删除该子树
     * @param node
     * @param element
     */
    public void delNode(BinNodePtr node, Object element) {
        //需要注意，我们判断的是当前结点的子结点是否需要删除，
        //而不是判断当前结点是否要删除
        if (node.equals(root) && node == null) {
            System.out.println("the tree is empty!");
        }
        if (node.getLeft() != null) {
            if (node.getLeft().getElement().equals(element)) {
                node.setLeft(null);
                return;
            } else {
                delNode(node.getLeft(), element);//向左子树递归删除
            }
        }
        if (node.getRight() != null) {
            if (node.getRight().getElement().equals(element)) {
                node.setRight(null);
                return;
            } else {
                delNode(node.getRight(), element);//向右子树递归删除
            }
        }
    }
    //前序遍历
    public void preOrder(BinNodePtr node) {
        if (node != null) {
            System.out.print(node.getElement() + " ");
            preOrder(node.getLeft());
            preOrder(node.getRight());
        } else return;
    }
    //中序遍历
    public void infixOrder(BinNodePtr node) {
        if (node != null) {
            infixOrder(node.getLeft());
            System.out.print(node.getElement() + " ");
            infixOrder(node.getRight());
        } else return;
    }
    //后序遍历
    public void postOrder(BinNodePtr node) {
        if (node != null) {
            postOrder(node.getLeft());
            postOrder(node.getRight());
            System.out.print(node.getElement() + " ");
        } else return;
    }
    //后序遍历并计算
    public void postOrderCalculate(BinNodePtr node) {
        if (node != null) {
            //遍历以后的根结点的值就是计算结果
            postOrderCalculate(node.getLeft());
            postOrderCalculate(node.getRight());
            System.out.print(node.getElement() + " ");
            if (node.getLeft()!=null&&node.getRight()!=null){
                switch ((char) node.getElement()) {
                    //加减乘除
                    case ('+'):
                        node.setElement((char) (((char) node.getLeft().getElement() - '0') +
                                ((char) node.getRight().getElement() - '0')+48));
                        break;
                    case ('-'):
                        node.setElement((char) (((char) node.getLeft().getElement() - '0') -
                                ((char) node.getRight().getElement() - '0')+48));
                        break;
                    case ('*'):
                        node.setElement((char) (((char) node.getLeft().getElement() - '0') *
                                ((char) node.getRight().getElement() - '0')+48));
                        break;
                    case ('/'):
                        node.setElement((char) (((char) node.getLeft().getElement() - '0') /
                                ((char) node.getRight().getElement() - '0')+48));
                        break;
                }
            }
        } else return;
    }

//
//    /**
//     * @Description: 利用前序、中序、后序分别查找element
//     * @Author yjq
//     * @Date 2021/9/21 21:05
//     * @Param node, element
//     * @Return 查找到返回该node，查找不到则返回null
//     * @Exception
//     */
//    //前序查找
//    public BinNodePtr preOrderSearch(BinNodePtr node, Object element) {
//        if (node != null) {
//            if (node.getElement().equals(element)) {
//                return node;//先比较当前结点
//            }
//            BinNodePtr temp = null;
//            if (node.getLeft() != null) {
//                temp = preOrderSearch(node.getLeft(), element);
//                //左子结点不为空则接着前序递归查找
//            }
//            if (temp != null) {
//                return temp;//返回值不为null说明找到了
//            }
//            if (node.getRight() != null) {
//                temp = preOrderSearch(node.getRight(), element);
//            }
//            return temp;
//        } else {
//            return null;
//        }
//    }
//
//    //中序查找
//    public BinNodePtr infixOrderSearch(BinNodePtr node, Object element) {
//        if (node != null) {
//            BinNodePtr temp = null;
//            if (node.getLeft() != null) {
//                temp = infixOrderSearch(node.getLeft(), element);
//                //左子结点不为空则接着前序递归查找
//            }
//            if (temp != null) {
//                return temp;//返回值不为null说明找到了
//            }
//            if (node.getElement().equals(element)) {
//                return node;//比较当前结点
//            }
//            if (node.getRight() != null) {
//                temp = infixOrderSearch(node.getRight(), element);
//            }
//            return temp;
//        } else {
//            return null;
//        }
//    }
//
//    //后序查找
//    public BinNodePtr postOrderSearch(BinNodePtr node, Object element) {
//        if (node != null) {
//            BinNodePtr temp = null;
//            if (node.getLeft() != null) {
//                temp = postOrderSearch(node.getLeft(), element);
//                //左子结点不为空则接着前序递归查找
//            }
//            if (temp != null) {
//                return temp;//返回值不为null说明找到了
//            }
//            if (node.getRight() != null) {
//                temp = postOrderSearch(node.getRight(), element);
//            }
//            if (temp != null) {
//                return temp;//返回值不为null说明找到了
//            }
//            if (node.getElement().equals(element)) {
//                return node;//比较当前结点
//            }
//            return temp;
//        } else {
//            return null;
//        }
//    }


}
